import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-29
 * Time: 9:22
 */
public class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                boolean[][] visited = new boolean[row][col];
                if (dfs(board, i, j, 0, word, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    public int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    private boolean dfs(char[][] board, int x, int y, int index, String word, boolean[][] visited) {
        // 没有匹配上
        if (board[x][y] != word.charAt(index)){
            return false;
        }
        // 匹配上了并且匹配完了
        if (index == word.length() - 1){
            return true;
        }
        // 标记为 已遍历
        visited[x][y] = true;
        // 匹配上了, 继续往下匹配
        for (int i = 0; i < 4; i++) {
            // 注意这里的 新的坐标就要用新的变量接收, 否则会叠加, 使坐标出错
            int row = x + next[i][0];
            int col = y + next[i][1];
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length){
                continue;
            }
            // 还没遍历时才能遍历
            if (!visited[row][col]){
                if (dfs(board, row, col, index+1, word, visited)){
                    return true;
                }
            }
        }
        // 回溯时不要忘记改回来
        visited[x][y] = false;
        return false;
    }
}
